#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void dfs(int step, int idx, int n, int k, vector<bool> &vis, vector<int>& tuple, vector<vector<int>>& ans){
        if(step == k){
            if(tuple.size()==k)ans.emplace_back(tuple);
            return;
        }
        for(int i=idx; i<=n; ++i){
            if(vis[i]) continue;
            tuple.push_back(i); vis[i] = true;
            dfs(step+1, i+1, n, k, vis, tuple, ans);
            vis[i] = false; tuple.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> tuple;
        vector<bool> vis(n+1, false);
        dfs(0, 1, n, k, vis, tuple, ans);
        return ans;
    }
};

int main(){

}